package Hot100;

/**
 * @author zhangmin
 * @create 2022-01-06 21:43
 */
public class numSquares279 {
    /**
     * 279. 完全平方数
     * 给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
     * 给你一个整数 n ，返回和为 n 的完全平方数的 最少数量 。
     * 1、dp，dp[i]表示少需要多少个数的平方来表示整数 i。 dp[i]=1+min(i-j^2)--1<=j<=根号i
     * 2、四平方和定理，任意一个正整数都可以被表示为至多四个正整数的平方和
     * 当且仅当 n ！= 4^k *(8m+7)时，n 可以被表示为至多三个正整数的平方和。
     *      此时，需要判断答案为1：则必有 n 为完全平方数
     *      答案为2，则有 n=a^2+b^2，我们只需要枚举所有的 a(1≤a≤n)，判断 n-a^2是否为完全平方数即可
     *      答案为3，用排除法
     * 当n ！= 4^k *(8m+7)时,n只能被表示为四个正整数的平方和，
     *
     * */
    public int numSquares1(int n) {
        int[] dp=new int[n+1];
        for (int i = 1; i <= n; i++) {
            int min=Integer.MAX_VALUE;
            for (int j = 1; j*j <= i; j++) {
                min=Math.min(min,dp[i-j*j]);
            }
            dp[i]=min+1;
        }
        return dp[n];
    }

    public int numSquares(int n) {
        if (isSquares(n)) return 1;
        if (isAnswer(n)) return 4;
        for (int i = 1; i*i <=n ; i++) {
            int j=n-i*i;
            if (isSquares(j)){
                //有 n=a^2+b^2，我们只需要枚举所有的 a(1≤a≤n)，判断 n-a^2是否为完全平方数即可
                return 2;
            }
        }
        return 3;
    }
    boolean isSquares(int x){
        int y= (int) Math.sqrt(x);
        return y*y==x;
    }
    boolean isAnswer(int x){
        while (x%4==0){
            x/=4;
        }
        return x%8==7;
    }
}
